package 牛客算法篇; /**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-02-21
 * Time:11:29
 */

/**
 *
 牛客算法篇:BM2 链表内指定区间反转
 描述
 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
 例如：
 给出的链表为 1→2→3→4→5→NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
 返回 1→4→3→2→5→NULL1→4→3→2→5→NULL.
 数据范围： 链表长度 0<size≤10000<size≤1000，0<m≤n≤size0<m≤n≤size，链表中每个节点的值满足 ∣val∣≤1000∣val∣≤1000
 要求：时间复杂度 O(n)O(n) ，空间复杂度 O(n)O(n)
 进阶：时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)
 示例1
 输入：
 {1,2,3,4,5},2,4
 返回值：
 {1,4,3,2,5}
 */
public class reverseBetween {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if (head == null){
            return null;
        }
        ListNode start = new ListNode(-1);
        start.next = head;
        ListNode cur = start;
        ListNode prev = cur.next;
        for (int i = 1; i < m; i++) {
            cur = cur.next;
            prev = prev.next;
        }
        for (int i = m; i < n; i++) {
            ListNode tmp = prev.next;
            prev.next = tmp.next;
            tmp.next = cur.next;
            cur.next = tmp;
        }
        return start.next;
    }
}
